#pragma once

#include <vector>

namespace solution_042
{

class Solution
{
public:
    int trap(const std::vector<int>& height)
    {
        int min_nonzero_id = -1;
        int max_nonzero_id = height.size();
        int min_top_id = 0;
        int max_top_id = height.size() - 1;

        int bar = 0;
        for (int i = 0; i < (int)height.size(); ++i) {
            auto h = height.at(i);
            bar += h;
            if (h) {
                max_nonzero_id = i;
                if (min_nonzero_id < 0)
                    min_nonzero_id = i;
                if (h > height.at(min_top_id))
                    min_top_id = max_top_id = i;
                else if (h == height.at(min_top_id))
                    max_top_id = i;
            }
        }

        if (min_nonzero_id < 0)
            return 0;

        int blank = 0;

        int last_top_h = height.at(min_nonzero_id);
        for (int i = min_nonzero_id; i <= min_top_id; ++i) {
            auto h = height.at(i);
            if (h > last_top_h) {
                blank += (h - last_top_h) * (i - min_nonzero_id);
                last_top_h = h;
            }
        }

        last_top_h = height.at(max_nonzero_id);
        for (int i = max_nonzero_id; i >= max_top_id; --i) {
            auto h = height.at(i);
            if (h > last_top_h) {
                blank += (h - last_top_h) * (max_nonzero_id - i);
                last_top_h = h;
            }
        }

        return (max_nonzero_id - min_nonzero_id + 1) * height.at(min_top_id) - blank - bar;
    }
};

}  /* namespace solution_042 */
